/**
 * 返回数组output，其中output[i]等于除了nums[i]之外各元素的乘积
 * 不能使用除法、时间复杂度O(n)、空间复杂度O(1)
 * @param {number[]} nums 
 * 动态规划:设置两个数组，保留从 当前位置开始到末尾的乘积、从头开始到当前位置的乘积
 * 空间复杂度O(1):直接在output上操作
 */
var productExceptSelf = function (nums) {
    // output初始化为1
    const result = Array(nums.length).fill(1)

    // output先记录 从头开始 到 当前位置上一位 的乘积
    let product = 1
    for (let i = 0; i < nums.length; i++) {
        result[i] = result[i] * product
        product = product * nums[i]
    }

    // 再记录从 当前位置+1 开始到 末尾 的乘积
    product = 1
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] = result[i] * product
        product = product * nums[i]
    }
    
    return result
}